package com.jxb.test20241216;

import com.jxb.first.ListNode;

import java.util.HashMap;
import java.util.Map;

public class LinkedListCycle_141 {

    public static void main(String[] args) {

    }

    //map
    public static boolean linkedListCycle1(ListNode head) {
        Map<Integer,Integer> map = new HashMap<>();
        int index = 0;
        while (head.next != null) {
            if (map.containsKey(head.val)) {
                return true;
            }else {
                map.put(head.val,index);
            }
            head = head.next;
            index++;
        }
        return false;
    }

    //弗洛伊德算法-通过快慢指针
    public static boolean linkedListCycle2(ListNode head) {
        ListNode fastP = head;
        ListNode slowP = head;
        while (head.next != null) {
            if (fastP.val == slowP.val) {
                return true;
            }
            fastP = head.next.next;
            slowP = head.next;
        }
        return false;
    }

    //弗洛伊德算法-返回环形链表的第一个节点
    public static ListNode linkedListCycle3(ListNode head) {
        ListNode fastP = head;
        ListNode slowP = head;
        boolean isCycle = false;
        //进行循环迭代，判断是否是相交链表，若是，重置慢指针
        while (head.next != null) {
            if (fastP.val == slowP.val) {
                slowP = head;
                isCycle = true;
                break;
            }
            fastP = fastP.next.next;
            slowP = slowP.next;
        }

        if (isCycle) {
            while (head.next != null) {
                if (fastP.val == slowP.val) {
                    return fastP;
                }
                fastP = fastP.next;
                slowP = slowP.next;
            }
        }

        return null;
    }

}
